package com.javabasic.algorithm.leetcode;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [1175. 质数排列 - 力扣（LeetCode）](https://leetcode.cn/problems/prime-arrangements/)
 * @since Created by work on 2022/6/30 23:31
 */
public class PrimeArrangements {

    final long MOD = 1000000007;

    /**
     * 筛法求素数+阶乘算法
     * @param n
     * @return
     */
    public int numPrimeArrangements(int n) {
        if (n < 3) {
            return 1;
        }
        int[] dp = new int[n+1];
        int half = n/2 + 1;
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < half; i++) {
            if (dp[i] == 1) {
                continue;
            }
            for (int j = 2; j*i <= n; j++) {
                dp[i*j] = 1;
            }
        }

        int nums = 0;
        for (int i = 2; i <= n; i++) {
            if (dp[i] == 0) {
                nums++;
            }
        }

        int nums2 = n-nums;
        int maxNum = Math.max(nums2, nums);
        long result = 1;
        for (int i = 2; i < maxNum; i++) {
            result = (result * i) % MOD;
            if (i == nums || i == nums2) {
                result = (result * result)%MOD;
            }
        }

        result = (result * maxNum) % MOD;
        if (nums2 == nums) {
            result = (result * result)%MOD;
        }

        return (int) result;
    }
}
